﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using ServiceNetworkDesign.Interface;
using ServiceNetworkDesign.Utilities;

namespace ServiceNetworkDesign.Impl
{
    /// <summary>
    /// Dijkstra算法求最短路径
    /// </summary>
    public class DShortCutPath:IPath
    {
        #region 
        //获取Dijkstra权值最小的路径
        public Path GetPath(List<Node> nodeList, string originID, string destID)
        {
            if (originID == destID) return new Path(nodeList,null,0);
            PlanCourse planCourse = new PlanCourse(nodeList, originID);

            Node curNode = this.GetMinWeightRudeNode(planCourse, nodeList, originID);

            #region 计算过程
            while (curNode != null)
            {
                PassedPath curPath = planCourse[curNode.ID];
                foreach (Edge edge in curNode.EdgeList)
                {
                    PassedPath targetPath = planCourse[edge.EndNodeID];
                    double tempWeight = curPath.Weight + edge.Weight;

                    if (tempWeight < targetPath.Weight)
                    {
                        targetPath.Weight = tempWeight;
                        targetPath.PassedIDList.Clear();
                        for (int i = 0; i < curPath.PassedIDList.Count; i++)
                        {
                            if(!targetPath.PassedIDList.Contains(curPath.PassedIDList[i]))
                            {
                             targetPath.PassedIDList.Add(curPath.PassedIDList[i]);
                            }
                        }
                        if (!targetPath.PassedIDList.Contains(curNode.ID))
                        {
                            targetPath.PassedIDList.Add(curNode.ID);
                        }
                    }
                }

                //标志为已处理
                planCourse[curNode.ID].BeProcessed = true;
                //获取下一个未处理节点
                curNode = this.GetMinWeightRudeNode(planCourse, nodeList, originID);
            }
            #endregion

            //表示计算结束
            return this.GetResult(nodeList, planCourse, destID);
        }
        #endregion

        #region private method
        #region GetResult
        //从PlanCourse表中取出目标节点的PassedPath，这个PassedPath即是结果
        private Path GetResult(List<Node> nodeList,PlanCourse planCourse, string destID)
        {
            PassedPath pPath = planCourse[destID];

            if (pPath.Weight == int.MaxValue)
            {
                Path result1 = new Path(null,null, int.MaxValue);
                return result1;
            }
            pPath.PassedIDList.Add(destID);
            Path result = new Path(nodeList,pPath.PassedIDList, pPath.Weight);

            return result;
        }
        #endregion

        #region GetMinWeightRudeNode
        //从PlanCourse取出一个当前累积权值最小，并且没有被处理过的节点
        private Node GetMinWeightRudeNode(PlanCourse planCourse, List<Node> nodeList, string originID)
        {
            double weight = double.MaxValue;
            Node destNode = null;

            foreach (Node node in nodeList)
            {
                if (node.ID == originID)
                {
                    continue;
                }

                PassedPath pPath = planCourse[node.ID];
                if (pPath.BeProcessed)
                {
                    continue;
                }

                if (pPath.Weight < weight)
                {
                    weight = pPath.Weight;
                    destNode = node;
                }
            }

            return destNode;
        }
        #endregion
        #endregion

    }
}
